package pers.whj.util.graph;

public class GraphLink<T> extends AbstractGraph<T> {
    protected Object[] mVertices;

    public GraphLink() {
        super();
        mVertices = new Object[mMaxVertices];
    }

    public GraphLink(int maxVertices) {
        super(maxVertices);
        mVertices = new Object[mMaxVertices];
    }

    @Override
    public boolean isCompleteGraph() {
        return mNumEdges == (long) mNumVertices / 2 * (mNumVertices - 1);
    }

    @Override
    public int getFirstNeighbor(int v) {
        checkIfVertexExists(v);
        Edge tmp = vertex(v).adj;
        return tmp == null ? -1 : tmp.dest;
    }

    @Override
    public int getNextNeighbor(int v, int w) {
        checkIfVerticesExist(v, w);
        Edge tmp = vertex(v).adj;
        while (tmp != null && tmp.dest != w) {
            tmp = tmp.next;
        }
        if (tmp != null && tmp.next != null) {
            return tmp.next.dest;
        }
        return -1;
    }

    @Override
    public int insertVertex(T vertex) {
        if (mNumVertices == mMaxVertices) {
            return -1;
        }
        mVertices[mNumVertices] = new Vertex<>(vertex, null);
        mNumVertices++;
        return mNumVertices - 1;
    }

    @Override
    public boolean insertEdge(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        if (v1 == v2) {
            return false;
        }
        Edge p = vertex(v1).adj;
        while (p != null && p.dest != v2) {
            p = p.next;
        }
        if (p != null) {
            return false;
        }
        p = new Edge(v2, vertex(v1).adj);
        vertex(v1).adj = p;
        vertex(v2).adj = new Edge(v1, vertex(v2).adj);
        mNumEdges++;
        return true;
    }

    @Override
    public boolean insertEdge(T vertex1, T vertex2) {
        return insertEdge(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    public boolean removeVertex(int v) {
        checkIfVertexExists(v);
        if (mNumVertices == 1) {
            mVertices[0] = null;
            mNumVertices = 0;
            return true;
        }
        Edge p, s, t;
        int k;
        Vertex<T> vertex = vertex(v);
        while (vertex.adj != null) {
            p = vertex.adj;
            k = p.dest;
            s = vertex(k).adj;
            t = null;
            while (s != null && s.dest != v) {
                t = s;
                s = s.next;
            }
            if (s != null) {
                if (t == null) {
                    vertex(k).adj = s.next;
                } else {
                    t.next = s.next;
                }
                s.next = null;
            }
            vertex.adj = p.next;
            p.next = null;
            mNumEdges--;
        }
        mNumVertices--;
        vertex.data = vertex(mNumVertices).data;
        vertex.adj = vertex(mNumVertices).adj;
        mVertices[mNumVertices] = null;
        p = vertex.adj;
        while (p != null) {
            s = vertex(p.dest).adj;
            while (s != null) {
                if (s.dest == mNumVertices) {
                    s.dest = v;
                    break;
                } else {
                    s = s.next;
                }
            }
            p = p.next;
        }
        return true;
    }

    @Override
    public boolean removeVertex(T vertex) {
        return removeVertex(getPosition(vertex));
    }

    @Override
    public boolean removeEdge(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        Edge p = vertex(v1).adj;
        Edge q = null;
        Edge s = p;
        while (p != null && p.dest != v2) {
            q = p;
            p = p.next;
        }
        if (p != null) {
            if (p == s) {
                vertex(v1).adj = p.next;
            } else {
                q.next = p.next;
            }
            p.next = null;
        } else {
            return false;
        }
        mNumEdges--;
        p = vertex(v2).adj;
        q = null;
        s = p;
        while (p.dest != v1) {
            q = p;
            p = p.next;
        }
        if (p == s) {
            vertex(v2).adj = p.next;
        } else {
            q.next = p.next;
        }
        p.next = null;
        return true;
    }

    @Override
    public boolean removeEdge(T vertex1, T vertex2) {
        return removeEdge(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    public boolean hasEdge(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        Edge p = vertex(v1).adj;
        while (p != null && p.dest != v2) {
            p = p.next;
        }
        return p != null;
    }

    @Override
    public boolean hasEdge(T vertex1, T vertex2) {
        return hasEdge(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    public void removeAllEdges() {
        Edge p;
        Vertex<T> vertex;
        for (int i = 0; i < mNumVertices; i++) {
            vertex = vertex(i);
            while (vertex.adj != null) {
                p = vertex.adj;
                vertex.adj = p.next;
                p.next = null;
            }
        }
        mNumEdges = 0;
    }

    @Override
    public void clear() {
        removeAllEdges();
        for (int i = 0; i < mNumVertices; i++) {
            mVertices[i] = null;
        }
        mNumVertices = 0;
    }

    @Override
    public boolean resize(int maxVertices) {
        if (maxVertices < mNumVertices) {
            return false;
        }
        if (maxVertices != mMaxVertices) {
            Object[] newVertices = new Object[maxVertices];
            System.arraycopy(mVertices, 0, newVertices, 0, mNumVertices);
            mVertices = newVertices;
            mMaxVertices = maxVertices;
        }
        return true;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    protected Vertex<T> vertex(int index) {
        // assert index is valid
        return (Vertex<T>) mVertices[index];
    }

    protected static class Edge {
        // position of another vertex int this edge
        int dest;
        Edge next;

        public Edge(int dest, Edge next) {
            this.dest = dest;
            this.next = next;
        }
    }

    protected static class Vertex<T> extends AbstractGraph.Vertex<T> {
        // the head of edge link
        Edge adj;

        public Vertex(T data, Edge adj) {
            super(data);
            this.adj = adj;
        }
    }
}